package gsw.tool.datastructure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import gsw.tool.common.Tool;
import gsw.tool.common.ToolShow;

/**
 * 有向带权邻接矩阵图
 *
 * @author Asus
 */
public class Graph<E> {
    // 顶点数组
    private E[] vertices;
    // 顶点之间的关系(即所有的边)
    private int[][] matrix;
    // 带权有向边
    public Edge[] edges;
    // 代表无穷大
    static final int M = 0xFFFFFF;

    public static void test() {
        Graph<String> grash = new Graph<String>();
        grash.add("A", new int[]{0, 1, M, 3, 2});
        grash.add("B", new int[]{1, 0, M, 7, 5});
        grash.add("C", new int[]{M, M, 0, 3, 4});
        grash.add("D", new int[]{3, 7, 3, 0, 9});
        grash.add("E", new int[]{2, 5, 4, 9, 0});
        grash.creatEdges();

//        grash.dfsErgodic();
//        grash.bfsErgodic();
//
//        //普里姆算法
//        List<Edge<String>> result = grash.prim("A");
//        ToolShow.log(result.toString());
//
//        //克鲁斯卡尔算法
//        List<Edge<String>> result2 = grash.kruskal();
//        ToolShow.log(result2.toString());

        //迪杰斯特拉
        int[] result3 = grash.dijkstra("D");
        for (int i : result3) {
            ToolShow.log("" + i);
        }
    }

    /**
     * 添加顶点
     *
     * @param e       顶点
     * @param weights 与其他顶点的边的权值
     */
    public void add(E e, int[] weights) {
        if (e == null || weights == null) {
            return;
        }
        //顶点数组大小
        int size = weights.length;
        int index = 0;
        if (vertices == null) {
            vertices = (E[]) new Object[size];
            matrix = new int[size][size];
        } else {
            size = vertices.length;
            for (int i = 0; i < size; i++) {
                if (vertices[i] == null) {
                    index = i;
                    break;
                }
            }
        }
        vertices[index] = e;
        matrix[index] = weights;
    }

    /**
     * 生成带权有向边
     */
    public void creatEdges() {
        if (edges != null || Tool.isEmpty(vertices)) {
            return;
        }
        int size = vertices.length;
        edges = new Edge[size * size];
        // 获取边
        int num = 0;
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) {
                int weight = matrix[i][j];
                if (weight > 0 && weight < M) {
                    edges[num++] = new Edge(vertices[i], vertices[j], weight);
                }
            }
        }
        edges = Arrays.copyOf(edges, num);
        Arrays.sort(edges);
    }

    /**
     * 深度优先遍历
     * 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：
     * 1. 首先访问出发点v，并将其标记为已访问过；
     * 2. 然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点均已被访问为止。
     * 3. 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
     */
    public void dfsErgodic() {
        if (Tool.isEmpty(vertices)) {
            return;
        }
        boolean[] visit = new boolean[vertices.length];
        for (int i = 0; i < vertices.length; i++) {
            dfs(visit, i);
        }
    }

    /**
     * 深度优先遍历
     *
     * @param visit 表示已经访问过的顶点
     * @param index 对应顶点的下标
     */
    public void dfs(boolean[] visit, int index) {
        if (visit[index] || Tool.isEmpty(matrix) || Tool.isEmpty(matrix[index])) {
            return;
        }

        visit[index] = true;
        ToolShow.log(vertices[index].toString());
        //邻接点
        int[] mat = matrix[index];
        for (int i = 0; i < mat.length; i++) {
            //权值为0代表自己，权值为M代表不可达
            if (mat[i] > 0 && mat[i] < M) {
                //优先访问第一个邻接点
                dfs(visit, i);
            }
        }
    }

    /**
     * 广度优先遍历
     * 遍历过程：
     * 1. 从图中某个顶点V0出发，并访问此顶点；
     * 2. 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；
     * 3. 重复步骤2，直到全部顶点都被访问为止。
     */
    public void bfsErgodic() {
        if (Tool.isEmpty(vertices)) {
            return;
        }
        boolean[] visit = new boolean[vertices.length];
        for (int i = 0; i < vertices.length; i++) {
            bfs(visit, i);
        }
    }

    /**
     * 广度优先遍历
     *
     * @param visit 表示已经访问过的顶点
     * @param index :对应顶点的下标
     */
    public void bfs(boolean[] visit, int index) {
        if (visit[index] || Tool.isEmpty(matrix) || Tool.isEmpty(matrix[index])) {
            return;
        }

        visit[index] = true;
        ToolShow.log(vertices[index].toString());
        //邻接点
        int[] mat = matrix[index];
        //已访问过的邻接点
        List<Integer> visitedE = new ArrayList<>();
        //先访问所有的邻接点
        for (int i = 0; i < mat.length; i++) {
            //不能重复访问
            if (!visit[i] && mat[i] > 0 && mat[i] < M) {
                visit[i] = true;
                ToolShow.log(vertices[i].toString());
                visitedE.add(i);
            }
        }
        //再以已经访问过的邻接点为起点，开始访问
        for (Integer m : visitedE) {
            dfs(visit, m);
        }
    }

    /**
     * Prim算法（普里姆算法）是一种最小生成树算法。Prim算法从任意一个顶点开始，每次选择一个与当前顶点集最近的一个顶点，并将两顶点之间的边加入到树中。
     * Prim算法在找当前最近顶点时使用到了贪婪算法。
     * 算法描述：
     * 1. 在一个加权连通图中，顶点集合V，边集合为E；
     * 2. 任意选出一个点作为初始顶点,标记为visit,计算所有与之相连接的点的距离，选择距离最短的，标记visit；
     * 3. 在剩下的点中，计算与已标记visit点距离最小的点，标记visit,证明加入了最小生成树;
     * 4. 重复3，直到所有点都被标记为visit。
     * 应用：计算铁路铺设长度
     */
    public List<Edge<E>> prim(E v) {
        int size = vertices == null ? 0 : vertices.length;
        if (size < 1) {
            return null;
        }
        List<Edge<E>> result = new ArrayList<>();
        //已标记的点
        List<Integer> visit = new ArrayList<>();
        visit.add(getIndex(v));
        for (int m = 0; m < size; m++) {
            int start = -1;
            int end = -1;
            int weight = M;
            //找到未访问的点中，距离当前最小生成树距离最小的点
            for (Integer n : visit) {
                //邻接点
                int[] mat = matrix[n];
                //找到最小邻接点的下标
                int min = getMin(mat, visit);
                if (min != -1 && mat[min] > 0 && mat[min] < weight) {
                    weight = mat[min];
                    start = n;
                    end = min;
                }
            }
            if (start > -1 && end > -1) {
                Edge<E> e = new Edge<>(vertices[start], vertices[end], weight);
                result.add(e);
                visit.add(end);
            }
        }
        return result;
    }

    /**
     * Kruskal算法(克鲁斯卡尔算法)是另一个计算最小生成树的算法，其算法原理如下：
     * - 首先，将所有的边排序，并创建一个空的顶点集合；
     * - 然后，按照权值的升序来选择边。如果起点和终点被相同的集合包含，就跳过。否则，将这条边插入最小生成树中。
     * - 然后更新顶点集合：如果所有的集合都不包含这条边的顶点，就新建一个集合，并将他的顶点添加进去；如果起点只被一个集合包含,那就把终点添加到这个集合；如果终点只被一个集合包含,那就把起点添加到这个集合；如果起点和终点分别被不同的集合包含,那就把这两个集合合并；
     * - 重复这个过程直到所有的边都探查过。
     */
    public List<Edge<E>> kruskal() {
        if (Tool.isEmpty(edges)) {
            return null;
        }
        int size = vertices.length;
        //已取出的线的顶点的集合
        List<List<E>> visitList = new ArrayList<>();
        List<Edge<E>> result = new ArrayList<>();
        for (int i = 0; i < edges.length; i++) {
            Edge<E> e = edges[i];
            //包含e的起点的集合
            List<E> start = null;
            //包含e的终点的集合
            List<E> end = null;
            for (List<E> eList : visitList) {
                if (Tool.isEmpty(eList)) {
                    break;
                }
                if (eList.contains(e.start) && !eList.contains(e.end)) {
                    start = eList;
                } else if (!eList.contains(e.start) && eList.contains(e.end)) {
                    end = eList;
                } else if (eList.contains(e.start) && eList.contains(e.end)) {
                    start = eList;
                    end = eList;
                }
            }
            //如果所有的集合都不包含这条边的顶点，就新建一个集合，并将他的顶点添加进去
            if (start == null && end == null) {
                List<E> list = new ArrayList<>();
                list.add(e.start);
                list.add(e.end);
                visitList.add(list);
                //如果起点只被一个集合包含,那就把终点添加到这个集合
            } else if (start != null && end == null) {
                start.add(e.end);
                //如果终点只被一个集合包含,那就把起点添加到这个集合
            } else if (start == null && end != null) {
                end.add(e.start);
                //如果起点和终点分别被不同的集合包含,那就把这两个集合合并
            } else if (start != end) {
                start.addAll(end);
                visitList.remove(end);
                //如果起点和终点被相同的集合包含，就跳过
            } else {
                break;
            }
            result.add(e);
        }
        return result;
    }

    /**
     * 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
     * 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
     * 操作步骤：
     * 1. 引进两个集合S和U，S的作用是记录已求出最短路径的顶点，而U中元素的下标表示顶点，U中元素的值表示该顶点到起点s的距离；
     * 2. 初始时，S只包含起点s；
     * 3. 从U中选出距离最短的顶点k，并将顶点k加入到S中；
     * 4. 利用k更新U的值。如果k与o直连，则取(S,o)的距离与(S,k)+(k,o)的距离的最小值作为s与o的距离。；
     * 5. 重复步骤3和4，直到遍历完所有顶点。
     * <p>
     * Dijkstra算法的证明
     * Dijkstra算法每次从更新后的U中，挑选权值最小的顶点k，然后把k的值当作起点s与顶点k的最短距离。然后用k更新其他未确定最短距离的顶点的值。下面证明它的正确性：
     * 我们把所有与s直接相连顶点叫s的直连点，所有与s不直接相连顶点叫s的非直连点。
     * 最初时，U中的值为s与直接点的权值，可以确定权值最小的顶点k的最短路径就是这个最小权值D，因为通过任意非直接点来连接s，都必须经过至少一个直连点。而s与非直连点的路径=s与直连点的路径+直连点与非直连点的路径，这个值肯定大于D，即D是s与其他点的距离的最小值，那么s与k的距离肯定不会小于D，即s与k的最短路径为D。
     * 然后，把k加入S，再利用k更新U的值。如果k与o直连，则取(S,o)的距离与(S,k)+(k,o)的距离的最小值作为s与o的距离。
     * 然后，在找U中权值最小的顶点k1，这个时候U中与s的所有可达点就相当于s的直连点。按照上面的推论，s与k1的最短路径即为U中的最小权值。
     * 重复以上步骤，即可找出所有顶点与s的最短距离。
     *
     * @param e:顶点
     * @return 顶点v到其余点的最小路径的集合
     */
    public int[] dijkstra(E e) {
        if (Tool.isEmpty(vertices)) {
            return null;
        }
        int size = vertices.length;
        //e的下标
        int index = getIndex(e);
        //已求出最短路径的顶点
        List<Integer> S = new ArrayList<>();
        S.add(index);
        //e与其他顶点的最短距离
        int[] U = Arrays.copyOf(matrix[index], size);
        for (int k = 0; k < size; k++) {
            //找出最短路径的顶点
            int update = getMin(U, S);
            if (update == -1) {
                break;
            }
            S.add(update);
            //更新U
            for (int i = 0; i < U.length; i++) {
                int weight = U[i];
                int newWeight = U[update] + matrix[update][i];
                if (weight > 0 && !S.contains(i) && newWeight < weight) {
                    U[i] = newWeight;
                }
            }
        }
        return U;
    }

    /**
     * 获取数组的最小权值的下标
     *
     * @param arr
     * @param visit
     * @return
     */

    public int getMin(int[] arr, List<Integer> visit) {
        int index = -1;
        if (Tool.isEmpty(arr)) {
            return index;
        }
        int weight = M;
        for (int i = 0; i < arr.length; i++) {
            if (visit != null && visit.contains(i)) {
                continue;
            }
            int w = arr[i];
            if (w > 0 && w < weight) {
                index = i;
                weight = w;
            }
        }
        return index;
    }

    /**
     * 获取元素位置
     *
     * @param e 查找的元素
     * @return
     */
    private int getIndex(E e) {
        if (Tool.isEmpty(vertices)) {
            return -1;
        }
        for (int j = 0; j < vertices.length; j++) {
            if (e == vertices[j]) {
                return j;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        if (vertices == null || matrix == null) {
            return "{}";
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < vertices.length; i++) {
            sb.append(vertices[i].toString() + "  ");
            int[] mat = matrix[i];
            if (mat != null) {
                for (int l : mat) {
                    sb.append((l == M ? "M" : l) + ",");
                }
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    /**
     * 边
     *
     * @author Asus
     */
    public static class Edge<E> implements Comparable<E> {
        // 起点
        public E start;
        // 终点
        public E end;
        // 权重
        public int weight;

        public Edge(E start, E end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        /**
         * 比较权重
         *
         * @param o 要比较的对象
         * @return 1代表大，0代表等于，-1代表小
         */
        @Override
        public int compareTo(Object o) {
            Edge e = (Edge) o;
            if (e == null) {
                return 1;
            }
            if (weight > e.weight) {
                return 1;
            } else if (weight == e.weight) {
                return 0;
            } else {
                return -1;
            }
        }

        @Override
        public String toString() {
            return "Edge [start=" + (start == null ? "null" : start.toString())
                    + ", end=" + (end == null ? "null" : end.toString())
                    + ", weight=" + weight + "]";
        }
    }
}
